Kombinatorika &
Logika Berhitung
👩🏫 Secara Formal:
Kombinatorika adalah cabang matematika yang berfokus pada penghitungan, penyusunan, dan pemilihan elemen dalam suatu himpunan. Topik ini menyumbang >25% soal OSN-K.
- Permutasi (P): Menyusun objek dengan memperhatikan urutan. (A,B) berbeda dengan (B,A).
- Kombinasi (C): Memilih objek tanpa memperhatikan urutan. (A,B) sama dengan (B,A).
- Pigeonhole Principle: Jika N merpati dimasukkan ke dalam M sarang (di mana N > M), maka setidaknya ada satu sarang yang berisi lebih dari satu merpati.
Analogi Jaman Now
Permutasi
Bayangin kamu bikin Password HP atau PIN ATM. Urutan angkanya sangat penting! Password `1234` tidak akan bisa dibuka dengan `4321` meskipun angkanya sama persis.
Kombinasi
Kayak kamu lagi milih Topping Seblak. Kamu pilih Kerupuk dan Sosis. Mau Abangnya masukin Sosis dulu baru Kerupuk, atau Kerupuk dulu baru Sosis, hasilnya tetap sama: Seblak Sosis Kerupuk!
Pigeonhole Principle
Kalau ada 4 sahabat nyari kosan, tapi sisa kamar kos di daerah itu cuma ada 3 kamar. Mustahil semuanya dapat kamar sendiri-sendiri kan? Pasti ada minimal 1 kamar yang bakal diisi oleh 2 orang atau lebih! Terdengar bodoh saking jelasnya, tapi logika ini super kuat untuk ngebuktiin banyak hal di Komputer Sains.
⚠️ Common Mistakes di OSN: Tertukar Kombinasi & Permutasi
Kesalahan paling sering terjadi adalah menggunakan rumus Permutasi pada kasus yang sebenarnya tidak mempedulikan urutan.
Cara membedakannya: Tanya pada dirimu sendiri, "Kalau urutannya dibalik, apakah dianggap kejadian yang BERBEDA?". Jika Ya (misal: jabatan Ketua & Wakil), gunakan Permutasi. Jika Tidak (misal: milih 3 orang anggota regu piket), gunakan Kombinasi.
Simulasi Pigeonhole Principle
Memasukkan N (jumlah Merpati) ke dalam M (jumlah Sarang) secara acak. Buktikan sendiri bahwa jika N > M, pasti ada sarang yang terisi > 1 merpati (berwarna merah).
Pencari Rute (Kombinatorika Grid)
Soal klasik OSN: "Berapa banyak cara berjalan dari Kiri Atas ke Kanan Bawah, jika hanya boleh bergerak ke KANAN atau ke BAWAH?" Ini adalah aplikasi dari rumus Kombinasi: C(Baris + Kolom, Baris).
⚠️ Common Mistakes: Hati-hati Faktorial Overflow!
Saat menghitung Kombinasi C(N, K) = N! / (K!(N-K)!) di program C++, jangan langsung menghitung nilai N! secara utuh karena Faktorial membesar dengan sangat cepat. Nilai 13! saja sudah melebihi kapasitas tipe data 32-bit Integer! Selalu gunakan fungsi pencoretan (simplifikasi pecahan) terlebih dahulu, atau gunakan segitiga Pascal / Dynamic Programming (DP) jika angkanya besar.